package binarytree;

import com.classroom.Firstclass.First;
import extend01.B;
import linklist.MyLinkedList;

import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:周次煜
 * Date: 2024-04-03
 * Time：14:59
 */
public class MyBinaryTree {


    public static class TreeNode {
        public TreeNode left;

        public TreeNode right;

        public  char val;


        public TreeNode(char val) {
            this.val = val;
        }
    }

    private TreeNode  root;

    // 构造二叉树
    public TreeNode createBinaryTree() {
        root=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode H=new TreeNode('H');
        TreeNode C=new TreeNode('C');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        root.left=B;
        B.left=D;
        B.right=E;
        E.right=H;
        root.right=C;
        C.left=F;
        C.right=G;

        return root;
    }


    // 字符串构造二叉树
   public int i=0;

    public TreeNode createBinaryTree1(String s) {

        TreeNode root=null;


        if (s.charAt(i) != '#') {
            root=new TreeNode(s.charAt(i));
            i++;
            root.left=createBinaryTree1(s);
            root.right=createBinaryTree1(s);
        } else {
            i++;
        }

        return root;

    }


    // 前序遍历
    public void FirstDisplay(TreeNode root) {
        if (root==null) {
            return;
        }

        System.out.print(root.val+" ");
        FirstDisplay(root.left);
        FirstDisplay(root.right);
    }


    // 非递归的前序遍历

    public  void  FirstDisplayNo(TreeNode root) {

        // 先创建一个栈来存放树的每个节点
        Stack<TreeNode> stack=new Stack<>();

        // 先把艮节点创建一遍
        TreeNode cur=root;

        /**
         * 外循环主要遍历 右边的节点
         * 用于出栈的数据
         * 并让节点向右移动
         */

        while (cur != null || !stack.empty()) {

            /**
             * 在这个内循环中
             * 当往左走就添加数据，一直到为 null 结束
             *  并进行打印
             */
            while (cur != null) {
                // 先打印
                System.out.print(cur.val+" ");

                // 打印完就入栈
                stack.add(cur);

                // 节点向左移动
                cur=cur.left;
            }

            // 出栈存放数据
            cur=stack.pop();

            // 并向右走
            cur=cur.right;

            // 当再次循环时，如果左边还有节点就会继续存放
        }


        System.out.println();

    }

    // 中序遍历
    public void middleDisplay(TreeNode root) {
        if (root==null) {
            return;
        }
        middleDisplay(root.left);
        System.out.print(root.val+" ");
        middleDisplay(root.right);
    }


    // 非递归的中序遍历
    public  void  middleDisplayNo (TreeNode root) {

        // 创建一个栈用于回退节点
        Stack<TreeNode> stack=new Stack<>();

        // 先放根节点
        TreeNode cur=root;

        /**
         * 外循环主要用于遍历 右边
         * 更是用于出栈的回退
         */

        while (cur != null || !stack.empty()) {

            /**
             * 内循环先遍历下去
             * 边遍历边存放
             */
            while (cur != null) {

                stack.add(cur);
                cur=cur.left;
            }

            // 出栈最后一个无左节点的左子树
            cur=stack.pop();
            // 打印该节点
            System.out.print(cur.val+" ");

            // 再往右走
            cur=cur.right;
        }
        System.out.println();
    }

    // 后序遍历
    public void lastDisplay(TreeNode root) {
        if (root==null) {
            return;
        }

        lastDisplay(root.left);
        lastDisplay(root.right);
        System.out.print(root.val+" ");

    }

    // 非递归的后序遍历
    public  void  lastDisplayNo (TreeNode root) {
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        TreeNode flg=null;
        while (cur != null || !stack.empty()) {
            while (cur != null) {

                stack.add(cur);
                cur=cur.left;
            }
            TreeNode top=stack.peek();
            if (top.right == null || flg==top.right) {
                System.out.print(top.val+" ");
                flg=top;
                stack.pop();
            } else {
                cur=top.right;
            }
        }
        System.out.println();
    }



    // 递归计算节点个数
    public int Size(TreeNode root) {
        if (root==null) {
            return 0;
        }

        return Size(root.left)+1+Size(root.right);
    }


    // 递归计算叶子个数
    public int leafSize(TreeNode root) {
        if (root==null) {
            return 0;
        }

        if (root.left==null && root.right==null) {
            return 1;
        }

        return leafSize(root.left)+leafSize(root.right);
    }


    // 非递归遍历节点个数
   public int nodeSize;

    public void setNodeSize(TreeNode root) {
        if (root==null) {
            return;
        }

        nodeSize++;

        setNodeSize(root.left);
        setNodeSize(root.right);
    }

    public int leafSize;

    public void setLeafSize(TreeNode root) {
        if (root==null) {
            return;
        }

        if (root.right==null && root.left==null) {
            leafSize++;
        }

        setLeafSize(root.left);
        setLeafSize(root.right);
    }


    // 查找节点
    public TreeNode find(TreeNode root, char val) {
        if(root==null) {
            return null;
        }



        if (Character.compare(val,root.val)==0) {
            return  root;
        }

        TreeNode node1=  find(root.left,val);
        if (node1 !=null) {
            return node1;
        }
        TreeNode node2= find(root.right,val);

        if (node2 !=null) {
            return node2;
        }
       return  null;

    }


    // 返回树的最大深度
    public int treeHeight(TreeNode root) {
        if (root==null) {
            return 0;
        }

        int leftnum=treeHeight(root.left);
        int rightnum=treeHeight(root.right);

        return leftnum>rightnum? leftnum+1: rightnum+1;
    }

    // 求树某深度的节点数
    public int treeIndexSize(TreeNode root , int key) {
        if (root==null) {
            return 0;
        }

        if (key==1) {
            return 1;
        }


        int left=treeIndexSize(root.left,key-1);


        int right=treeIndexSize(root.right,key-1);


        // key 位置开始查找节点 并 一直累加
        return left+right+1;
    }

    // 求树某深度的节点数
    public int treeIndexlength(TreeNode root , int key) {
        if (root==null) {
            return 0;
        }

        if (key==1) {
            return 1;
        }


        int left=treeIndexlength(root.left,key-1);


        int right=treeIndexlength(root.right,key-1);


        // 一直返回该 key 位置的节点
        return left+right;
    }


    public List<List<Character>> lists=new ArrayList<>();

    //层序遍历
   public void levelOrder(TreeNode root,int i) {
        if (root==null) {

            return;
        }

        if (lists.size()==i) {
            lists.add(new ArrayList<>());
        }

        lists.get(i).add(root.val);

        levelOrder(root.left,i+1);
        levelOrder(root.right,i+1);
    }


    // 判断一棵树是不是完全二叉树
   public boolean isCompleteTree(TreeNode root) {
       if (root==null) {
           return  true;
       }



        return CheckTreeCount(root) >= 0 ;
    }

    private int CheckTreeCount(TreeNode root) {
       if (root==null) {
           return  0;
       }

       int left=CheckTreeCount(root.left);
       if (left<0) {
           return -1;
       }
       int right=CheckTreeCount(root.right);
        if(right<0) {
            return  -1;
        }
        if (left<right) {
            return -1;
        } else {
            return Math.max(left,right)+1;
        }

   }


        public TreeNode buildTree(char[] preorder, char[] inorder) {

            return  CreateTreeChild(preorder,inorder,0,0,inorder.length-1);
        }

        private  TreeNode CreateTreeChild(char[]preorder,char[]inorder,int preIndex,int ib,int ie) {
                if (ib>ie) {
                    return null;
                }

            TreeNode root=new TreeNode(preorder[preIndex]);
            int find1 =findTreeIndex(inorder,preorder[preIndex]);
            preIndex++;


            root.left=CreateTreeChild(preorder,inorder,preIndex,ib,find1-1);
            root.right=CreateTreeChild(preorder,inorder,preIndex,find1+1,ie);

            return  root;
        }

    private int findTreeIndex(char[] inorder,char key) {
        for (int j = 0; j < inorder.length; j++) {
            if (inorder[j] == key) {
                return  j;
            }
        }

        return  -1;
    }



    public String tree2str(TreeNode root) {
        StringBuilder sbr= new StringBuilder();


        return  sbr.toString();
    }

    private  void CreateString(TreeNode root,StringBuilder s) {
       if (root==null) {
           return;
       }

       s.append(root.val);

       if (root.left != null) {
           s.append("(");
           CreateString(root.left,s);
           s.append(")");

       } else {
           if (root.right != null) {
               s.append("()");
           } else {
               return;
           }
       }

       if (root.right != null) {
           s.append("(");
           CreateString(root.right,s);
           s.append(")");
       }
    }


    public Character lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
       Stack<Character> stack1=new Stack<>();
       Stack<Character> stack2=new Stack<>();
       CreateStack(root,stack1,p);
       CreateStack(root,stack2,q);
       return insertRoot(stack1,stack2);
    }

    private boolean CreateStack(TreeNode root,Stack<Character> stack,TreeNode key) {


       if (root==null ) {
           return  false;
       }
        stack.push(root.val);
        if (root.val==key.val) {
            return true;
        }

       boolean b1=CreateStack(root.left,stack,key);
       if (b1) {

           return  true;
       }

       boolean b2=CreateStack(root.right,stack,key);
       if (b2) {

           return  true;
       }

       stack.pop();
       return  false;
    }

    public Character insertRoot(Stack<Character> sp,Stack<Character> sq) {
       int szp=sp.size();
       int szq=sq.size();

       if (szq>szp) {
           int count=szq-szp;
           while (count > 0) {
               sq.pop();
               count--;
           }
       } else {
           int count=szp-szq;
           while (count > 0) {
               sp.pop();
               count--;
           }
       }

       while (!sp.empty()) {
           char cp=sp.peek();
           char cq=sq.peek();
           if (cp==cq) {
                return cp;
           }

           sp.pop();
           sq.pop();
       }

       return null;
    }


   public  List<List<Character>> ls;
    public List<List<Character>> levelOrderBottom(TreeNode root) {
            ls=new ArrayList<>();
            setLs(root,ls,0);
            swapLs(ls);
            return ls;
    }

    private  void  setLs(TreeNode root, List<List<Character>> lists ,int i) {
            if (root==null) {
                return;
            }

            if (lists.size()==i) {
                lists.add(new ArrayList<Character>());
            }

            lists.get(i).add(root.val);
            setLs(root.left,lists,i+1);
            setLs(root.right,lists,i+1);

    }

    private  void  swapLs(List<List<Character>> lists) {
        int left=0,right=lists.size()-1;
        while (left < right) {
           List<Character> tmp=lists.get(left);
           lists.set(left,lists.get(right));
           lists.set(right,tmp);
           left++;
           right--;
        }
    }

}

